import java.util.*;

public class Test1 {
    public int minSubArrayLen(int target, int[] nums){
        int n=nums.length,sum=0,width=-1;
        int max=Integer.MAX_VALUE;
        for (int right = 0,left=0; right <n;right++) {

            if(sum<=target) {
                sum += nums[right];
            }
            while(sum>target){
                sum-=nums[left++];
                 width=Math.min(max,right-left+1);
            }
        }
        return width;
    }
    //不含有重复字符的最长子串的长度
    public static int lengthOfLongestSubstring(String ss) {
        int n = ss.length(), len = 0;
        char[] s = ss.toCharArray();
        int[] hash = new int[128];
        for (int left = 0, right = 0; right < n; right++) {
            hash[s[right]]++;
            while (hash[s[right]] > 1) {
                hash[s[left++]]--;//出窗口
            }
            len = Math.max(len, right - left + 1);
        }
       return len;
    }
    public static int longestOnes1(int[] nums, int k){
        //暴力枚举
        int n=nums.length;
        int len=0;
        for (int i = 0; i < n; i++) {
            int zeros=0;
            for (int j = i; j < n; j++) {
                if(nums[j]==0){
                    zeros++;
                }
                len=Math.max(len,j-i+1);
                if(zeros>k){
                    break;
                }

            }
        }
        return len;
    }
    public static int longestOnes(int[] nums, int k){
        int n=nums.length,zeros=0;
        int len=0;
        for (int right = 0,left=0; right < n; right++) {
            if(nums[right]==0){
                zeros++;
            }
            while (zeros>k){
                if(nums[left++]==0){
                    zeros--;
                }
            }
            len=Math.max(len,right-left+1);
        }
        return len;
    }
    //正难则反
    public static int minOperations(int[] nums, int x){
        int n=nums.length,all=0,sum=0,len=-1;
        //int min=10001;
        for (int i = 0; i < n; i++) {
            all+=nums[i];

        }
        int target=all-x;
        // System.out.println("min"+min);
        if(target<0) return -1;

        for (int right = 0,left=0; right < n; right++) {
            sum+=nums[right];
            while (sum>target){
                sum-=nums[left++];
            }if(sum==target){
                len=Math.max(len,right-left+1);
            }
        }
        return len==-1?-1:n-len;
    }

    public static int totalFruit1(int[] fruits){
        int n=fruits.length,ret=0;
        int[]hash=new int[n+1];
        for (int right = 0,left=0,kinds=0; right < n; right++) {
            if(hash[fruits[right]]==0){
                kinds++;
            }
            hash[fruits[right]]++;
            while(kinds>2){
                hash[fruits[left]]--;
                if(hash[fruits[left]]==0){
                    kinds--;
                }
                left++;
            }
            ret=Math.max(ret,right-left+1);
        }
        return ret;
    }
    public static int totalFruit(int[] fruits){
        HashMap<Integer,Integer>hashMap=new HashMap<>();
        int n=fruits.length,ret=0;
        for (int right = 0,left=0; right < n; right++) {
            int in=fruits[right];
            hashMap.put(in,hashMap.getOrDefault(in,0)+1);
            while(hashMap.size()>2){
                int out=fruits[left++];
                hashMap.put(out,hashMap.get(out)-1);
                if(hashMap.get(out)==0){
                    hashMap.remove(out);
                }
            }
            ret=Math.max(ret,right-left+1);
        }
        return ret;
    }
    //找异或词
    public static boolean check(int[]hash1,int[]hash2){
        for (int i = 0; i < 26; i++) {
            if(hash1[i]!=hash2[i]){
                return false;
            }
        }
        return true;
    }
    public static List<Integer> findAnagrams(String ss, String pp){
        List<Integer>ret=new ArrayList<>();
        char[]s=ss.toCharArray(),p=pp.toCharArray();
        int[]hash2=new int[26],hash1=new int[26];
        int n=s.length;
        for(char x:p){
            hash2[x - 'a']++;
        }
        for (int r = 0,l=0,count=0; r < n; r++) {
            int in=s[r]-'a';
            hash1[in]++;
            if(hash1[in]<=hash2[in]){
                count++;
            }
            if(r-l+1>p.length){
                 int out=s[l]-'a';
                hash1[out]--;
                l++;
                if(hash1[out]<hash2[out]){
                    count--;
                }
            }
            if(count==p.length){
                ret.add(l);
            }
        }
        return ret;
    }
    public static List<Integer> findSubstring(String s, String[] words){
        List<Integer>ret=new ArrayList<>();
        Map<String,Integer>map1=new HashMap<>();
        Map<String,Integer>map2=new HashMap<>();
        int len=words[0].length();
        for(String x:words){
            map1.put(x,map1.getOrDefault(x,0)+1);
        }
        for (int i = 0; i < len; i++) {
            for(int left=i,right=i,count=0;right+len<=s.length();right+=len){
                String in= s.substring(right,right+len);
                map2.put(in,map2.getOrDefault(in,0)+1);
                if(map2.get(in)<=map1.getOrDefault(in,0)) count++;
                if(right-left+1>words.length*len){
                    String out=s.substring(left,left+len);
                    left+=len;
                    map2.put(out,map2.get(out)-1);
                    if(map2.get(out)<map1.getOrDefault(out,0)) count--;
                }
                if(count==words.length){
                    ret.add(left);
                }
            }
        }
        return  ret;
    }
    public static boolean check1(int[] hash1,int[] hash2){
        for (int i = 0; i < hash1.length; i++) {
            if(hash1[i]!=0){
                if(hash1[i]>hash2[i]){
                    return false;
                }
            }
        }
        return true;
    }
    public static String minWindow(String ss, String tt) {
        String s1=new String();
        int minLen=Integer.MAX_VALUE;
        int begin=0,kinds=0;
        int[]hash1=new int[62],hash2=new int[62];
        char[]t=tt.toCharArray(),s=ss.toCharArray();
        for(char x:t)  if(hash1[x-'A']++ == 0) kinds++;
        for (int r = 0,l=0,count=0; r < s.length; r++)
        {
            int in=s[r]-'A';
            hash2[in]++;
            if(hash2[in]==hash1[in]) count++;
            while(count==kinds)
            {
                if(minLen>r-l+1)
                {
                    minLen=r-l+1;
                    begin=l;
                    s1=ss.substring(begin,begin+minLen);
                }
                int out=s[l]-'A';
                if(hash1[out] == hash2[out]--) count--;
                l++;
            }
        }
        return s1;
    }

    public static void main(String[] args) {
        String S="ADOBECODEBANC";
        String T="ABC";
        String ret=minWindow(S,T);
        System.out.println(ret);
    }

    public static void main7(String[] args) {
        String s="barfoothefoobarman";
        String[]words={"foo","bar"};
        List<Integer>ret= findSubstring(s,words);
        for (int x: ret){
            System.out.print(x+" ");
        }
    }

    public static void main6(String[] args) {
        String s="cbaebabacd";
        String p="abc";
        List<Integer>ret=findAnagrams(s,p);
        for (int x: ret){
            System.out.print(x+" ");
        }

    }

    public static void main5(String[] args) {
        int []nums={1,2,3,2,2};
        System.out.println(totalFruit(nums));
    }

    public static void main4(String[] args) {
        int[]nums={5};
        System.out.println(minOperations(nums, 5));
    }
    public static void main3(String[] args) {
        int[]nums={1,1,1,0,0,0,1,1,1,1,0};
        System.out.println(longestOnes(nums, 2));

    }

    public static void main2(String[] args) {
        String s="abcabcbb";
        int ret=lengthOfLongestSubstring(s);
        System.out.println(ret);
    }
    public static void main1(String[] args) {
        int []arr={1,1,1,1};
        Test1 test=new Test1();
        System.out.println(test.minSubArrayLen(1, arr));

    }
}
